#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 2606. 找到最大开销的子字符串
class Solution1
{
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) 
    {
        int mapping[26]{};
        iota(mapping, mapping + 26, 1);
        for(int i = 0; i < chars.size(); ++i) 
            mapping[chars[i] - 'a'] = vals[i];

        int ret = 0, f = 0;
        for(char ch : s)
        {
            f = max(f, 0) + mapping[ch - 'a'];
            ret = max(ret, f);
        }

        return ret;
    }
};

// 1493. 删掉一个元素以后全为 1 的最长子数组
class Solution2
{
public:
    int longestSubarray(vector<int>& nums) 
    {
        int n = nums.size(), left = 0, right = 0, ret = 0;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i]) ++right;
            else left = right, right = 0;
            ret = max(ret, left + right);
        }
        return ret == n ? n - 1 : ret;
    }
};

// 840. 矩阵中的幻方
class Solution3
{
private:
    bool magic(vector<int>& m)
    {
        int count[16]{};
        for(int x : m)
        {
            if(++count[x] > 1 || x > 9) return false;
        }

        return m[0] + m[1] + m[2] == 15
            && m[3] + m[4] + m[5] == 15
            && m[6] + m[7] + m[8] == 15
            && m[0] + m[3] + m[6] == 15
            && m[1] + m[4] + m[7] == 15
            && m[2] + m[5] + m[8] == 15
            && m[0] + m[4] + m[8] == 15
            && m[2] + m[4] + m[6] == 15;
    }

public:
    int numMagicSquaresInside(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid.size();
        if(m < 3 || n < 3) return 0;

        int ret = 0;
        for(int i = 0; i <= m - 3; ++i)
        {
            for(int j = 0; j <= n - 3; ++j)
            {
                if(grid[i + 1][j + 1] != 5) continue;
                
                vector<int> v;
                for(int row = i; row < i + 3; ++row)
                {
                    for(int col = j; col < j + 3; ++col)
                    {
                        v.push_back(grid[row][col]);
                    }
                }
                ret += magic(v);
            }
        }

        return ret;
    }
};

// 1003. 检查替换后的词是否有效
class Solution4
{
public:
    bool isValid(string s) 
    {
        string ret;
        for(char ch : s)
        {
            if(ch == 'c')
            {
                if(ret.size() < 2) return false;
                else if(ret.back() == 'b' && ret[ret.size() - 2] == 'a') 
                {
                    ret.pop_back();
                    ret.pop_back();
                }
                else return false;
            }
            else
                ret += ch;
        }
        return ret.empty();
    }
};

// 1432. 改变一个整数能得到的最大差值
class Solution5
{
public:
    int maxDiff(int num) 
    {
        auto change = [&](int x, int y)
        {
            string num_s = to_string(num);
            for(char& digit : num_s)
            {
                if(digit - '0' == x) digit = '0' + y;
            }
            return num_s;
        };

        int minNum = num, maxNum = num;
        for(int x = 0; x < 10; ++x)
        {
            for(int y = 0; y < 10; ++y)
            {
                string ret = change(x, y);
                if(ret[0] != '0')
                {
                    int ret_i = stoi(ret);
                    minNum = min(minNum, ret_i);
                    maxNum = max(maxNum, ret_i);
                }
            }
        }

        return maxNum - minNum;
    }
};

// 1315. 祖父节点值为偶数的节点和
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution6
{
public:
    int sumEvenGrandparent(TreeNode* root) 
    {
        int ret = 0;
        function<void(TreeNode*, TreeNode*, TreeNode*)> dfs = [&](TreeNode* cur, TreeNode* fa, TreeNode* ffa) -> void
        {
            if(cur == nullptr) return;

            dfs(cur->left, cur, fa);
            dfs(cur->right, cur, fa);
            if(ffa && ffa->val % 2 == 0) ret += cur->val;
        };

        dfs(root, nullptr, nullptr);
        return ret;
    }
};